λ¬Έμ
κ°λ°μ μΆμ μΌλ‘ μΈκ³ μ΅κ³ μ κ°λΆκ° λ μ΄νΌμΉλ μ€νΈλ μ€λ₯Ό λ°μ λλ©΄ μ΄λ₯Ό νκΈ° μν΄ μ€νλΌμΈ λ§€μ₯μ μΌνμ νλ¬ κ°κ³€ ν©λλ€. μ΄νΌμΉλ μΌνμ ν λλ©΄ λ§€μ₯ μ§μ΄λμ νΉμ λ²μμ 물건λ€μ λͺ¨λ μΉμΈμ΄ ꡬ맀νλ μ΅κ΄μ΄ μμ΅λλ€. μ΄λ λ μ€νΈλ μ€λ₯Ό νκΈ° μν΄ λ³΄μ λ§€μ₯μ μΌνμ νλ¬ κ° μ΄νΌμΉλ μ΄μ μ²λΌ μ§μ΄λμ νΉμ λ²μμ 보μμ λͺ¨λ ꡬ맀νλ νΉλ³ν μλ λͺ©μ μ λ¬μ±νκ³ μΆμμ΅λλ€. μ§μ΄λ λͺ¨λ μ’ λ₯μ 보μμ μ μ΄λ 1κ° μ΄μ ν¬ν¨νλ κ°μ₯ μ§§μ ꡬκ°μ μ°Ύμμ ꡬ맀
μλ₯Ό λ€μ΄ μλ μ§μ΄λλ 4μ’ λ₯μ 보μ(RUBY, DIA, EMERALD, SAPPHIRE) 8κ°κ° μ§μ΄λ μμμ λλ€.
| μ§μ΄λ λ²νΈ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 보μ μ΄λ¦ | DIA | RUBY | RUBY | DIA | DIA | EMERALD | SAPPHIRE | DIA |
μ§μ΄λμ 3λ²λΆν° 7λ²κΉμ§ 5κ°μ 보μμ ꡬ맀νλ©΄ λͺ¨λ μ’ λ₯μ 보μμ μ μ΄λ νλ μ΄μμ© ν¬ν¨νκ² λ©λλ€.
μ§μ΄λμ 3, 4, 6, 7λ²μ 보μλ§ κ΅¬λ§€νλ κ²μ μ€κ°μ νΉμ ꡬκ°(5λ²)μ΄ λΉ μ§κ² λλ―λ‘ μ΄νΌμΉμ μΌν μ΅κ΄μ λ§μ§ μμ΅λλ€.
μ§μ΄λ λ²νΈ μμλλ‘ λ³΄μλ€μ μ΄λ¦μ΄ μ μ₯λ λ°°μ΄ gemsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§λλ€. μ΄λ λͺ¨λ 보μμ νλ μ΄μ ν¬ν¨νλ κ°μ₯ μ§§μ ꡬκ°μ μ°Ύμμ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ. κ°μ₯ μ§§μ ꡬκ°μ μμ μ§μ΄λ λ²νΈμ λ μ§μ΄λ λ²νΈλ₯Ό μ°¨λ‘λλ‘ λ°°μ΄μ λ΄μμ return νλλ‘ νλ©°, λ§μ½ κ°μ₯ μ§§μ ꡬκ°μ΄ μ¬λ¬ κ°λΌλ©΄ μμ μ§μ΄λ λ²νΈκ° κ°μ₯ μμ ꡬκ°μ return ν©λλ€.
μ νμ¬ν
-
gems λ°°μ΄μ ν¬κΈ°λ 1 μ΄μ 100,000 μ΄νμ λλ€.
- gems λ°°μ΄μ κ° μμλ μ§μ΄λμ λμ΄λ 보μμ λνλ λλ€.
- gems λ°°μ΄μλ 1λ² μ§μ΄λλΆν° μ§μ΄λ λ²νΈ μμλλ‘ λ³΄μμ΄λ¦μ΄ μ°¨λ‘λλ‘ μ μ₯λμ΄ μμ΅λλ€.
- gems λ°°μ΄μ κ° μμλ κΈΈμ΄κ° 1 μ΄μ 10 μ΄νμΈ μνλ²³ λλ¬Έμλ‘λ§ κ΅¬μ±λ λ¬Έμμ΄μ λλ€.
μ μΆλ ₯ μ
| gems | return | |
|---|---|---|
| ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] | [3, 7] | |
| ["AA", "AB", "AC", "AA", "AC"] | [1, 3] | |
| ["XYZ", "XYZ", "XYZ"] | [1, 1] | |
| ["ZZZ", "YYY", "NNNN", "YYY", "BBB"] | [1, 5] |
π Logic
while (true) {
// μμ§ μ’
λ₯κ° λ€ μ μ±μμ§ κ²½μ°
if (gemTypes != gemMap.size()) {
if (right == gems.length) break;
else {
// 보μμ ꡬ맀νλ κ²½μ°λ‘, Mapμ κ°μλ₯Ό μ¦κ°μν€λ©΄μ 보μμ μ μ₯
gemMap.put(gems[right], gemMap.getOrDefault(gems[right], 0) + 1);
right++;
}
}
// μ’
λ₯κ° λ€ μ±μμ§ κ²½μ°
if (gemTypes == gemMap.size()) {
// μ΄μ κΉμ§ ꡬν ꡬκ°μ κΈΈμ΄μ λΉκ΅νμ¬ μλ€λ©΄ update
if (right - left < distance) {
distance = right - left;
start = left;
end = right;
}
// κ΅¬κ° μ€μ΄κΈ° μν΄ μ μΌ μ 보μ 1κ° μμ
gemMap.put(gems[left], gemMap.get(gems[left]) - 1);
// 보μ κ°μκ° 0κ°μ΄λ©΄ mapμμ μμ
if (gemMap.get(gems[left]) == 0) gemMap.remove(gems[left]);
left++;
}
}
left,rightλΌλ ν¬μΈν°λ₯Ό μ¬μ©νμ¬ λ³΄μ μ§μ΄λλ₯Ό νμνλ€.-
보μ μ§μ΄λμ λμΈ λͺ¨λ μ’ λ₯μ 보μμ νλ μ΄μ ꡬ맀ν κ²½μ°μ, κ·Έλ μ§ μμ κ²½μ°λ‘ λλλ€.
- λ€ μ±μμ§μ§ μμ κ²½μ°λ ꡬ맀ν 보μμ κ°μ μ 보λ₯Ό μ
λ°μ΄νΈνλ©΄μ
Mapμ μ μ₯νκ³ , - λ€ μ±μμ§ κ²½μ°λ μ΅μ ꡬκ°μΈμ§ νμΈνκ³ μμμ λΆν° 보μ κ°μλ₯Ό νλμ© μ€μΈλ€.
- λ€ μ±μμ§μ§ μμ κ²½μ°λ ꡬ맀ν 보μμ κ°μ μ 보λ₯Ό μ
λ°μ΄νΈνλ©΄μ
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
// 보μμ μμΉλ₯Ό μ μ₯ν Map
Map<String, Integer> gemMap = new HashMap<>();
// μ§μ΄λμ μλ 보μμ μ€λ³΅ μμ΄ μ μ₯ν Set
Set<String> gemSet = new HashSet<>(Arrays.asList(gems));
// 보μμ μ’
λ₯λ₯Ό ꡬνκΈ° μν΄ Set μ¬μ©
int gemTypes = gemSet.size();
int distance = Integer.MAX_VALUE;
int start = 0, end = 0, left = 0, right = 0;
while (true) {
// μμ§ μ’
λ₯κ° λ€ μ μ±μμ§ κ²½μ°
if (gemTypes != gemMap.size()) {
if (right == gems.length) break;
else {
// 보μμ ꡬ맀νλ κ²½μ°λ‘, Mapμ κ°μλ₯Ό μ¦κ°μν€λ©΄μ 보μμ μ μ₯
gemMap.put(gems[right], gemMap.getOrDefault(gems[right], 0) + 1);
right++;
}
}
// μ’
λ₯κ° λ€ μ±μμ§ κ²½μ°
if (gemTypes == gemMap.size()) {
// μ΄μ κΉμ§ ꡬν ꡬκ°μ κΈΈμ΄μ λΉκ΅νμ¬ μλ€λ©΄ update
if (right - left < distance) {
distance = right - left;
start = left;
end = right;
}
// κ΅¬κ° μ€μ΄κΈ° μν΄ μ μΌ μ 보μ 1κ° μμ
gemMap.put(gems[left], gemMap.get(gems[left]) - 1);
// 보μ κ°μκ° 0κ°μ΄λ©΄ mapμμ μμ
if (gemMap.get(gems[left]) == 0) gemMap.remove(gems[left]);
left++;
}
}
return new int[] {start + 1, end};
}
}
βοΈ Review
- ν¬ ν¬μΈν°λ₯Ό μ¬μ©ν΄μΌ νλ λ¬Έμ μμ λ°λ‘ μ μ μμμ§λ§, ν¬ ν¬μΈν°λ₯Ό μ¬μ©νμ§ μκ³ κ° λ³΄μλ€μ μμΉλ₯Ό μ μ₯νκ³ μ΄ μμΉ μ 보λ§μ μ¬μ©ν΄μ ν λ°©λ²μ μμκΉλ₯Ό κ³ λ―Όν΄λ³΄μλ€.
- ν¬ ν¬μΈν° μκ³ λ¦¬μ¦μ μ¬μ©νλ κ°μ₯ νν μκ° λΆλΆ λ°°μ΄ ν©μ ꡬνλ λ¬Έμ μλλ°, μ΄λ₯Ό μ¬κΈ°μ μ΄λ»κ² μ λͺ©μν€λμ§ μλ¬Έμ΄μλ€.
- ν¬ ν¬μΈν° μκ³ λ¦¬μ¦μ΄ κ³ λ₯μ΄ λ¬Έμ μλ μ¬μ©λλλ°, ν λ² νΌμ νμ΄λ΄μΌκ² λ€...
π μΆμ²
Programmers : https://programmers.co.kr/learn/courses/30/lessons/67258